package Top_Interview_Questions.Stack;

/**
 * @Author: 吕庆龙
 * @Date: 2020/1/9 9:27
 *
 */
public class _0084 {

    public static void main(String[] args) {
        int[] s = {2,1,5,6,2,3};
        largestRectangleArea2(s);
    }



    /**
     * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution
     * /xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-1-7/
     *
     * 执行时间超%94
     *
     * 解析:
     * 1.感觉像是用了动态规划,这里的l不能用 i - 1替代。不然while循环会陷入死循环。
     */
    public static int largestRectangleArea2(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }
        //求每个柱子的左边第一个小的柱子的下标
        int[] leftLessMin = new int[heights.length];
        leftLessMin[0] = -1;
        for (int i = 1; i < heights.length; i++) {
            int l = i - 1;
            while (l >= 0 && heights[l] >= heights[i]) {
                l = leftLessMin[l];   //1.
            }
            leftLessMin[i] = l;
        }

        //求每个柱子的右边第一个小的柱子的下标
        int[] rightLessMin = new int[heights.length];
        rightLessMin[heights.length - 1] = heights.length;
        for (int i = heights.length - 2; i >= 0; i--) {
            int r = i + 1;
            while (r <= heights.length - 1 && heights[r] >= heights[i]) {
                r = rightLessMin[r];
            }
            rightLessMin[i] = r;
        }

        //求包含每个柱子的矩形区域的最大面积，选出最大的
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            int area = (rightLessMin[i] - leftLessMin[i] - 1) * heights[i];
            maxArea = Math.max(area, maxArea);
        }
        return maxArea;
    }



    /**
     * 方法3: 分治法
     * https://blog.csdn.net/qq_39382769/article/details/80788293
     *
     * 优化的分治法是用线段树写的,暂时没看
     *
     * 解析:
     * 1.这里不要传heights.length,不然Math.max(heights[minindex] * (end - start + 1)
     * 这里会数组越界。具体可以debug看
     * 2.这里可以写成int i = start + 1;也就是自己不要跟自己比较了
     */
    public static int calculateArea(int[] heights, int start, int end) {
        if (start > end)
            return 0;
        int minindex = start;
        for (int i = start; i <= end; i++)//2.
            if (heights[minindex] > heights[i])
                minindex = i;
        return Math.max(heights[minindex] * (end - start + 1), Math.max(calculateArea(heights, start, minindex - 1), calculateArea(heights, minindex + 1, end)));
    }
    public static int largestRectangleArea1(int[] heights) {
        return calculateArea(heights, 0, heights.length-1);//1.
    }


    /**
     * 方法 2：优化的暴力
     */
    public static int largestRectangleArea(int[] heights) {
        int maxarea = 0;
        for (int i = 0; i < heights.length; i++) {
            int minheight = Integer.MAX_VALUE;
            for (int j = i; j < heights.length; j++) {
                minheight = Math.min(minheight, heights[j]);
                maxarea = Math.max(maxarea, minheight * (j - i + 1));
            }
        }
        return maxarea;
    }

}
